#include <iostream>
#include <vector>
using namespace std;

int findMin(const vector<int> &input) {
  int begin = 0;
  int end = input.size() - 1;
  int mid = begin;
  while (input[begin] >= input[end]) {
    if (end - begin == 1) {
      return input[end];
    }
    mid = begin + ((end - begin) >> 1);
    if (input[begin] == input[end] &&
        input[begin] == input[mid]) {
      int ret = input[begin];
      for (int i = begin + 1; i <= end; ++i) {
        if (input[i] < ret) {
          ret = input[i];
        }
      }
      return ret;
    }

    if (input[mid] >= input[begin]) {
      begin = mid;
    } else if (input[mid] <= input[end]) {
      end = mid;
    }
  }
  return input[mid];
}

int main() {
  // 正常输入
  vector<int> input1 = {3, 4, 5, 1, 2};
  int result1 = findMin(input1);
  cout << "result1: " << result1 << " expected: 1" << endl;
  
  // 排序输入，mid的初始值是begin
  vector<int> input2 = {1, 2, 3, 4, 5};
  int result2 = findMin(input2);
  cout << "result2: " << result2 << " expected: 1" << endl;

  // input[begin] = input[mid] = input[end]
  vector<int> input3 = {1, 0, 1, 1, 1};
  int result3 = findMin(input3);
  cout << "result3: " << result3 << " expected: 0" << endl;
}
